// Time:  O(n)
// Space: O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include "head/TreeNode.h"
#include <vector>
#include <queue>
#include <cassert>
#include<iostream>
class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            std::vector<int> v;
            for (int i=0; i<len; i++) {
                TreeNode *node = q.front();
                q.pop();
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
                v.push_back(node->val);
            }
            res.push_back(std::move(v));
        }
        return res;
    }
};



// Helper function to create a binary tree
TreeNode* createBinaryTree(const std::vector<int>& values) {
    if (values.empty()) return nullptr;
    TreeNode* root = new TreeNode(values[0]);
    std::queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (i < values.size()) {
        TreeNode* node = q.front();
        q.pop();
        if (values[i] != -1) {
            node->left = new TreeNode(values[i]);
            q.push(node->left);
        }
        i++;
        if (i < values.size() && values[i] != -1) {
            node->right = new TreeNode(values[i]);
            q.push(node->right);
        }
        i++;
    }
    return root;
}

// Test case
int main() {
    // Create a binary tree
    // Tree structure:
    //     3
    //    / \
    //   9  20
    //      / \
    //     15  7
    std::vector<int> values = {3, 9, 20, -1, -1, 15, 7};
    TreeNode* root = createBinaryTree(values);

    // Create the Solution object
    Solution sol;

    // Perform level-order traversal
    std::vector<std::vector<int>> result = sol.levelOrder(root);

    // Expected level-order traversal: {{3}, {9, 20}, {15, 7}}
    std::vector<std::vector<int>> expected = {{3}, {9, 20}, {15, 7}};

    // Verify the result
    assert(result == expected);

    std::cout << "Test passed!" << std::endl;

    return 0;
}